package offer_test_40;

import java.util.Arrays;

import org.omg.CORBA.ARG_IN;

//输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。
//要求时间复杂度为O(n)。例如输入的数组为{1，-2,3,10，-4,7,2，-5}，和最大的子数组为{3,10，-4,7,2}。和为18
public class eleven_MaxCountOfSubArray {
	public static void main(String[] args) {
		int[] array={1,-2,3,10,-4,7,2,-5};
		int max=array[0];
		for(int i=1;i<array.length;i++){
			int[] temp=Arrays.copyOfRange(array, 0, i);
			int tempmax=getMax(temp);
			if(tempmax>max){
				max=tempmax;
			}
		}
		System.out.println(max);
	}
	//动态规划，返回数组以末尾元素为尾部的子数组的 最大max值。
	public static int getMax(int[] array) {
		if (array.length == 1) {
			return array[0];
		}
		int[] temparray = Arrays.copyOfRange(array, 0, array.length - 1);
		if(getMax(temparray)<=0){
			return array[array.length-1];
		}
		int rs=0;
		if (array.length >1) {
			int now = array[array.length - 1];
			rs= Math.max(now, now + getMax(temparray));
		}
		return rs;
	}
}
